
#include <stdio.h>
#include <iostream>
#include <set>

namespace leetcode160 {

	struct ListNode {
		int val;
		ListNode *next;
		ListNode(int x, ListNode *n = NULL): val(x), next(n) {}
	};

	class Solution {
		public:
		static ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

			// 最简单的
			ListNode *a = headA;
			/*while(a != NULL) {
				ListNode *b = headB;
				while (b != NULL) {
					if (a == b ) {
						return b;
					}
					b = b->next;	
				}
				a = a->next;
			}*/
			// 利用了std::set的特点  值唯一性,自动排序,基于红黑树,  但不支持随机访问和线程不安全
			/*
			std::set<ListNode *> check_set;
			while(a != NULL) {
				check_set.insert(a);
				a = a->next;
			}

			ListNode *b = headB;
			while (b != NULL) {
				auto it = check_set.find(b);
				if (it != check_set.end()) {
					return b;
				}
				b = b->next;
			}
			return NULL;
			*/

			// 这种解法性能是最高的， log(n+m)   
			// 理解这个解法的核心是，两个指针走的步数最终是一样的，肯定会相交，不会导致死循环
			ListNode *b = headB;
			while (a != b) {
				std::cout << "---" << std::endl;
				a = (a == NULL) ? headB : a->next;
				b = (b == NULL) ? headA : b->next;
			}
			return a;	
		}
	};

	void test() {
		ListNode *a = new ListNode{5};
		ListNode *a1 = new ListNode{4};
		a1->next = a;
		ListNode *a2 = new ListNode{8};
		a2->next = a1;
		ListNode *a3 = new ListNode{1};
		a3->next = a2;
		ListNode *a4 = new ListNode{4};
		a4->next = a3;

		ListNode *b1 = new ListNode{1};
		b1->next = a2;
                ListNode *b2 = new ListNode{6};
                b2->next = b1;
                ListNode *b3 = new ListNode{5};
                b3->next = b2;

		ListNode * res = Solution::getIntersectionNode(a4, b3);
		if (res == NULL) {
			std::cout << "leetcode160 res null" << std::endl;
			return;
		} 
		std::cout << "leetcode160 res:" << res->val << std::endl;
	}
}


int main() {
	leetcode160::test();	
	return 0;
};
